package array.medium;

import java.util.Arrays;

/**
 * 1863. 找出所有子集的异或总和再求和
 */
public class subsetXORSum {
    public static void main(String[] args) {
        subsetXORSum subsetXOR = new subsetXORSum();
        int[] test1 = {5, 1, 6};
//        System.out.println(myCode(test1, 0));
//        System.out.println(subsetXOR.subsetXORSum(test1));
        subsetXOR.dfs(1, 5, test1);
        System.out.println(subsetXOR.result);
    }

    public static int myCode(int[] nums, int count) {
        if (nums.length == 1) {
            return count + nums[0];
        }
        int xor = 0;
        for (int num : nums) {
            xor = xor ^ num;
            count = count + xor;
        }
        int[] num1 = Arrays.copyOfRange(nums, 1, nums.length);
        return myCode(num1, count);
    }

    /**
     * 深度优先算法
     */
    int result = 0;
    public int subsetXORSum(int[] nums) {
        for(int i = 0; i < nums.length; i++)
            dfs(i + 1, nums[i], nums);
        return result;
    }

    public void dfs(int temp, int sum, int[] nums){

        if(temp == nums.length) result += sum;
        else{
            dfs(temp + 1, sum, nums);
            dfs(temp + 1, sum ^ nums[temp], nums);
        }
    }
}
